use std::marker::PhantomData;
use std::mem::{size_of, swap};
use std::ptr::{copy, write, NonNull};

pub trait NodeBase<T> {
    fn create(val: T) -> Box<Self>;
    fn set_value(&mut self, val: T);
    fn value(&self) -> T;
    fn set_prev(&mut self, prev: Option<NonNull<Self>>);
    fn prev(&self) -> Option<NonNull<Self>>;
    fn prev_nth(&self, i: u64) -> Option<NonNull<Self>>;
    fn set_next(&mut self, next: Option<NonNull<Self>>);
    fn next(&self) -> Option<NonNull<Self>>;
    fn next_nth(&self, i: u64) -> Option<NonNull<Self>>;
    fn unwrap(self: Box<Self>) -> T {
        self.value()
    }
}

pub trait ChainBase<T> {
    fn new() -> Self;
    fn push_head(&mut self, val: T);
    fn pop_head(&mut self) -> Option<T>;
    fn push(&mut self, val: T);
    fn pop(&mut self) -> Option<T>;
    fn size(&self) -> u64;
    fn insert(&mut self, pos: u64, val: T);
    fn update(&mut self, pos: u64, val: T);
    fn delete(&mut self, pos: u64) -> Option<T>;
    fn clear(&mut self);
    fn at(&self, pos: u64) -> Option<T>;
    fn swap(&mut self, x: u64, y: u64);
    fn to_vector(&self) -> Vec<T>;
}

pub trait Search<T> {
    fn index(&self, val: &T) -> Option<u64>;
    fn index_from(&self, val: &T, offset: u64) -> Option<u64>;
    fn index_last_of(&self, val: &T) -> Option<u64>;
    fn count(&self, val: &T) -> u64;
}

pub struct Node<T> {
    value: T,
    next: Option<NonNull<Node<T>>>,
}

impl<T: Clone> NodeBase<T> for Node<T> {
    #[inline]
    fn create(val: T) -> Box<Self> {
        Box::<Self>::new(Node {
            value: val,
            next: None,
        })
    }

    #[inline]
    fn set_value(&mut self, val: T) {
        unsafe { write(&mut self.value, val) }
    }

    #[inline]
    fn value(&self) -> T {
        self.value.clone()
    }

    #[inline]
    fn set_prev(&mut self, _prev: Option<NonNull<Self>>) {
        panic!("single-linked node does not have prev attribute ")
    }

    #[inline]
    fn prev(&self) -> Option<NonNull<Self>> {
        panic!("single-linked node does not have prev attribute ")
    }

    #[inline]
    fn prev_nth(&self, _i: u64) -> Option<NonNull<Self>> {
        panic!("single-linked node does not have prev attribute ")
    }

    #[inline]
    fn set_next(&mut self, next: Option<NonNull<Self>>) {
        self.next = next
    }

    #[inline]
    fn next(&self) -> Option<NonNull<Self>> {
        self.next
    }

    #[inline]
    fn next_nth(&self, i: u64) -> Option<NonNull<Self>> {
        if i == 0 {
            return Some(self.into());
        }
        let mut node = self.next;
        for _ in 1..i {
            match node {
                None => {
                    node = None;
                    break;
                }
                Some(ptr) => unsafe {
                    node = (*ptr.as_ptr()).next();
                },
            }
        }
        node
    }
}

pub struct DNode<T> {
    value: T,
    prev: Option<NonNull<DNode<T>>>,
    next: Option<NonNull<DNode<T>>>,
}

impl<T: Clone> NodeBase<T> for DNode<T> {
    #[inline]
    fn create(val: T) -> Box<Self> {
        Box::<Self>::new(DNode {
            value: val,
            prev: None,
            next: None,
        })
    }

    #[inline]
    fn set_value(&mut self, val: T) {
        unsafe { write(&mut self.value, val) }
    }

    #[inline]
    fn value(&self) -> T {
        self.value.clone()
    }

    #[inline]
    fn set_prev(&mut self, prev: Option<NonNull<Self>>) {
        self.prev = prev
    }

    #[inline]
    fn prev(&self) -> Option<NonNull<Self>> {
        self.prev
    }

    #[inline]
    fn prev_nth(&self, i: u64) -> Option<NonNull<Self>> {
        if i == 0 {
            return Some(self.into());
        }
        let mut node = self.prev;
        for _ in 1..i {
            match node {
                None => {
                    node = None;
                    break;
                }
                Some(ptr) => unsafe {
                    node = (*ptr.as_ptr()).prev();
                },
            }
        }
        node
    }

    #[inline]
    fn set_next(&mut self, next: Option<NonNull<Self>>) {
        self.next = next
    }

    #[inline]
    fn next(&self) -> Option<NonNull<Self>> {
        self.next
    }

    #[inline]
    fn next_nth(&self, i: u64) -> Option<NonNull<Self>> {
        if i == 0 {
            return Some(self.into());
        }
        let mut node = self.next;
        for _ in 1..i {
            match node {
                None => {
                    node = None;
                    break;
                }
                Some(ptr) => unsafe {
                    node = (*ptr.as_ptr()).next();
                },
            }
        }
        node
    }
}

#[derive(Clone, Default)]
pub struct Chain<N> {
    size: u64,
    head: Option<NonNull<N>>,
    tail: Option<NonNull<N>>,
    marker: PhantomData<Box<N>>,
}

impl<N, T> ChainBase<T> for Chain<N>
where
    T: Clone + Sized,
    N: NodeBase<T>,
{
    #[inline]
    fn new() -> Self {
        Chain {
            size: 0,
            head: None,
            tail: None,
            marker: PhantomData,
        }
    }

    #[inline]
    fn push_head(&mut self, val: T) {
        let mut node = N::create(val);
        node.set_next(self.head);
        let node = Some(Box::leak(node).into());
        if self.tail.is_none() {
            self.tail = node;
        }
        self.head = node;
        self.size += 1;
    }

    #[inline]
    fn pop_head(&mut self) -> Option<T> {
        self.head.map(|node| unsafe {
            let node = Box::from_raw(node.as_ptr());
            self.head = node.next();
            if self.head.is_none() {
                self.tail = None;
            }
            self.size -= 1;
            N::unwrap(node)
        })
    }

    #[inline]
    fn push(&mut self, val: T) {
        unsafe {
            let node = Some(Box::leak(N::create(val)).into());
            match self.tail {
                None => self.head = node,
                Some(tail) => (*tail.as_ptr()).set_next(node),
            }
            self.tail = node;
            self.size += 1;
        }
    }

    #[inline]
    fn pop(&mut self) -> Option<T> {
        self.tail.map(|node| unsafe {
            let node = Box::from_raw(node.as_ptr());
            match self.head == self.tail {
                true => {
                    self.head = None;
                    self.tail = None;
                }
                false => {
                    let node = (*self.head.unwrap().as_ptr()).next_nth(self.size - 2);
                    (*node.unwrap().as_ptr()).set_next(None);
                    self.tail = node;
                }
            }
            self.size -= 1;
            N::unwrap(node)
        })
    }

    #[inline]
    fn size(&self) -> u64 {
        self.size
    }

    #[inline]
    fn insert(&mut self, pos: u64, val: T) {
        assert!(pos <= self.size, "insertion is out of index");
        unsafe {
            match pos {
                0 => self.push_head(val),
                n if n == self.size => self.push(val),
                n => {
                    let prev = (*self.head.unwrap().as_ptr()).next_nth(n - 1);
                    let ptr = prev.unwrap().as_ptr();
                    let mut node = N::create(val);
                    node.set_next((*ptr).next());
                    let node = Some(Box::leak(node).into());
                    (*ptr).set_next(node);
                    self.size += 1;
                }
            }
        }
    }

    #[inline]
    fn delete(&mut self, pos: u64) -> Option<T> {
        unsafe {
            match pos {
                0 => self.pop_head(),
                n if n == self.size - 1 => self.pop(),
                n if n >= self.size => None,
                _ => {
                    let prev = (*self.head.unwrap().as_ptr()).next_nth(pos - 1);
                    let ptr = prev.unwrap().as_ptr();
                    let node = Box::from_raw((*ptr).next().unwrap().as_ptr());
                    (*ptr).set_next(node.next());
                    self.size -= 1;
                    Some(N::unwrap(node))
                }
            }
        }
    }

    #[inline]
    fn clear(&mut self) {
        *self = Self::new();
    }

    #[inline]

    fn update(&mut self, pos: u64, val: T) {
        unsafe {
            match pos {
                n if self.size == 0 || n >= self.size => {}
                n if n == self.size - 1 => (*self.tail.unwrap().as_ptr()).set_value(val),
                0 => (*self.head.unwrap().as_ptr()).set_value(val),
                _ => {
                    let node = (*self.head.unwrap().as_ptr()).next_nth(pos);
                    (*node.unwrap().as_ptr()).set_value(val)
                }
            }
        }
    }

    #[inline]
    fn at(&self, pos: u64) -> Option<T> {
        unsafe {
            match pos {
                n if self.size == 0 || n >= self.size => None,
                n if n == self.size - 1 => Some((*self.tail.unwrap().as_ptr()).value()),
                0 => Some((*self.head.unwrap().as_ptr()).value()),
                _ => {
                    let node = (*self.head.unwrap().as_ptr()).next_nth(pos);
                    Some((*node.unwrap().as_ptr()).value())
                }
            }
        }
    }

    #[inline]
    fn swap(&mut self, x: u64, y: u64) {
        assert!(x < self.size && y < self.size, "invalid index for chain");
        if x != y {
            unsafe {
                let (x, y) = match x < y {
                    true => (x, y),
                    false => (y, x),
                };
                let px = (*self.head.unwrap().as_ptr()).next_nth(x).unwrap().as_ptr();
                let py = match y {
                    y if y == self.size - 1 => self.tail.unwrap().as_ptr(),
                    y => (*px).next_nth(y - x).unwrap().as_ptr(),
                };
                let tmp = (*px).value();
                (*px).set_value((*py).value());
                (*py).set_value(tmp);
            }
        }
    }

    #[inline]
    fn to_vector(&self) -> Vec<T> {
        let mut container = Vec::<T>::with_capacity(self.size as usize);
        unsafe {
            let mut node = self.head;
            while let Some(n) = node {
                container.push((*n.as_ptr()).value());
                node = (*n.as_ptr()).next();
            }
        }
        container
    }
}

#[derive(Clone, Default)]
pub struct Table<N> {
    size: u64,
    head: Option<NonNull<N>>,
    tail: Option<NonNull<N>>,
    marker: PhantomData<Box<N>>,
}

impl<N, T> ChainBase<T> for Table<N>
where
    T: Clone + Sized,
    N: NodeBase<T>,
{
    #[inline]
    fn new() -> Self {
        Table {
            size: 0,
            head: None,
            tail: None,
            marker: PhantomData,
        }
    }

    #[inline]
    fn push_head(&mut self, val: T) {
        let mut node = N::create(val);
        node.set_next(self.head);
        let node = Some(Box::leak(node).into());
        match self.head {
            None => self.tail = node,
            Some(head) => unsafe { (*head.as_ptr()).set_prev(node) },
        }
        self.head = node;
        self.size += 1;
    }

    #[inline]
    fn pop_head(&mut self) -> Option<T> {
        self.head.map(|node| unsafe {
            let node = Box::from_raw(node.as_ptr());
            self.head = node.next();
            match self.head {
                None => self.tail = None,
                Some(head) => (*head.as_ptr()).set_prev(None),
            }
            self.size -= 1;
            N::unwrap(node)
        })
    }

    #[inline]
    fn push(&mut self, val: T) {
        let mut node = N::create(val);
        node.set_prev(self.tail);
        let node = Some(Box::leak(node).into());
        match self.tail {
            None => self.head = node,
            Some(tail) => unsafe { (*tail.as_ptr()).set_next(node) },
        }
        self.tail = node;
        self.size += 1;
    }

    #[inline]
    fn pop(&mut self) -> Option<T> {
        self.tail.map(|node| unsafe {
            let node = Box::from_raw(node.as_ptr());
            self.tail = node.prev();
            match self.tail {
                None => self.head = None,
                Some(tail) => (*tail.as_ptr()).set_next(None),
            }
            self.size -= 1;
            N::unwrap(node)
        })
    }

    #[inline]
    fn size(&self) -> u64 {
        self.size
    }

    #[inline]
    fn insert(&mut self, pos: u64, val: T) {
        assert!(pos <= self.size, "insertion is out of index");
        unsafe {
            match pos {
                0 => self.push_head(val),
                n if n == self.size => self.push(val),
                n => {
                    let (prev, next) = match (2 * n) < self.size {
                        true => {
                            let ptr = (*self.head.unwrap().as_ptr())
                                .next_nth(pos - 1)
                                .unwrap()
                                .as_ptr();
                            (ptr, (*ptr).next().unwrap().as_ptr())
                        }
                        false => {
                            let ptr = (*self.tail.unwrap().as_ptr())
                                .prev_nth(self.size - 1 - pos)
                                .unwrap()
                                .as_ptr();
                            ((*ptr).prev().unwrap().as_ptr(), ptr)
                        }
                    };
                    let mut node = N::create(val);
                    node.set_prev((*next).prev());
                    node.set_next((*prev).next());
                    let node = Some(Box::leak(node).into());
                    (*prev).set_next(node);
                    (*next).set_prev(node);
                    self.size += 1;
                }
            }
        }
    }

    #[inline]
    fn delete(&mut self, pos: u64) -> Option<T> {
        unsafe {
            match pos {
                0 => self.pop_head(),
                n if n == self.size - 1 => self.pop(),
                n if n >= self.size => None,
                n => {
                    let (prev, node) = match (2 * n) < self.size {
                        true => {
                            let ptr = (*self.head.unwrap().as_ptr())
                                .next_nth(pos - 1)
                                .unwrap()
                                .as_ptr();
                            (ptr, Box::from_raw((*ptr).next().unwrap().as_ptr()))
                        }
                        false => {
                            let ptr = (*self.tail.unwrap().as_ptr())
                                .prev_nth(self.size - 1 - pos)
                                .unwrap()
                                .as_ptr();
                            ((*ptr).prev().unwrap().as_ptr(), Box::from_raw(ptr))
                        }
                    };
                    (*prev).set_next(node.next());
                    (*node.next().unwrap().as_ptr()).set_prev(node.prev());
                    self.size -= 1;
                    Some(N::unwrap(node))
                }
            }
        }
    }

    #[inline]
    fn clear(&mut self) {
        *self = Self::new();
    }

    #[inline]
    fn update(&mut self, pos: u64, val: T) {
        unsafe {
            match pos {
                n if self.size == 0 || n >= self.size => {}
                n if n == self.size - 1 => (*self.tail.unwrap().as_ptr()).set_value(val),
                0 => (*self.head.unwrap().as_ptr()).set_value(val),
                n => {
                    let node = match (2 * n) < self.size {
                        true => (*self.head.unwrap().as_ptr()).next_nth(pos),
                        false => (*self.tail.unwrap().as_ptr()).prev_nth(self.size - 1 - pos),
                    };
                    (*node.unwrap().as_ptr()).set_value(val)
                }
            }
        }
    }

    #[inline]
    fn at(&self, pos: u64) -> Option<T> {
        unsafe {
            match pos {
                n if self.size == 0 || n >= self.size => None,
                n if n == self.size - 1 => Some((*self.tail.unwrap().as_ptr()).value()),
                0 => Some((*self.head.unwrap().as_ptr()).value()),
                n => {
                    let node = match (2 * n) < self.size {
                        true => (*self.head.unwrap().as_ptr()).next_nth(pos),
                        false => (*self.tail.unwrap().as_ptr()).prev_nth(self.size - 1 - pos),
                    };
                    Some((*node.unwrap().as_ptr()).value())
                }
            }
        }
    }

    #[inline]
    fn swap(&mut self, x: u64, y: u64) {
        assert!(x < self.size && y < self.size, "invalid index for chain");
        if x != y {
            unsafe {
                let (x, y) = match x < y {
                    true => (x, y),
                    false => (y, x),
                };
                let (px, py) = match 2 * x > self.size {
                    true => {
                        let node_y = (*self.tail.unwrap().as_ptr()).prev_nth(self.size - 1 - y);
                        let _py = node_y.unwrap().as_ptr();
                        let _px = (*_py).prev_nth(y - x).unwrap().as_ptr();
                        (_px, _py)
                    }
                    false => {
                        let _px = (*self.head.unwrap().as_ptr()).next_nth(x).unwrap().as_ptr();
                        let _py = match y {
                            y if (2 * y) > (self.size + x) => (*self.tail.unwrap().as_ptr())
                                .prev_nth(self.size - 1 - y)
                                .unwrap()
                                .as_ptr(),
                            y => (*_px).next_nth(y - x).unwrap().as_ptr(),
                        };
                        (_px, _py)
                    }
                };
                let tmp = (*px).value();
                (*px).set_value((*py).value());
                (*py).set_value(tmp);
            }
        }
    }

    #[inline]
    fn to_vector(&self) -> Vec<T> {
        let mut container = Vec::<T>::with_capacity(self.size as usize);
        unsafe {
            let mut node = self.head;
            while let Some(n) = node {
                container.push((*n.as_ptr()).value());
                node = (*n.as_ptr()).next();
            }
        }
        container
    }
}

#[derive(Clone, Default)]
pub struct Ring<N> {
    size: u64,
    node: Option<NonNull<N>>,
    marker: PhantomData<Box<N>>,
}

impl<N, T> ChainBase<T> for Ring<N>
where
    T: Clone + Sized,
    N: NodeBase<T>,
{
    #[inline]
    fn new() -> Self {
        Ring {
            size: 0,
            node: None,
            marker: PhantomData,
        }
    }

    #[inline]
    fn push_head(&mut self, val: T) {
        unsafe {
            let node = match self.node {
                None => {
                    let boxed = N::create(val);
                    let node: Option<NonNull<N>> = Some(Box::leak(boxed).into());
                    let pnode = node.unwrap().as_ptr();
                    (*pnode).set_prev(node);
                    (*pnode).set_next(node);
                    node
                }
                Some(next) => {
                    let boxed = N::create(val);
                    let node: Option<NonNull<N>> = Some(Box::leak(boxed).into());
                    let prev = (*next.as_ptr()).prev();
                    let pnode = node.unwrap().as_ptr();
                    (*pnode).set_prev(prev);
                    (*pnode).set_next(self.node);
                    (*prev.unwrap().as_ptr()).set_next(node);
                    (*next.as_ptr()).set_prev(node);
                    node
                }
            };
            self.node = node;
        }
        self.size += 1;
    }

    #[inline]
    fn pop_head(&mut self) -> Option<T> {
        self.node.map(|node| unsafe {
            let node = Box::from_raw(node.as_ptr());
            if self.size == 1 {
                self.node = None;
            } else {
                let (prev, next) = (node.prev().unwrap().as_ptr(), node.next().unwrap().as_ptr());
                (*prev).set_next(node.next());
                (*next).set_prev(node.prev());
                self.node = node.next();
            }
            self.size -= 1;
            N::unwrap(node)
        })
    }

    #[inline]
    fn push(&mut self, val: T) {
        unsafe {
            let node = match self.node {
                None => {
                    let boxed = N::create(val);
                    let node: Option<NonNull<N>> = Some(Box::leak(boxed).into());
                    let pnode = node.unwrap().as_ptr();
                    (*pnode).set_prev(node);
                    (*pnode).set_next(node);
                    node
                }
                Some(prev) => {
                    let boxed = N::create(val);
                    let node: Option<NonNull<N>> = Some(Box::leak(boxed).into());
                    let next = (*prev.as_ptr()).next();
                    let pnode = node.unwrap().as_ptr();
                    (*pnode).set_prev(self.node);
                    (*pnode).set_next(next);
                    (*prev.as_ptr()).set_next(node);
                    (*next.unwrap().as_ptr()).set_prev(node);
                    node
                }
            };
            self.node = node;
        }
        self.size += 1;
    }

    #[inline]
    fn pop(&mut self) -> Option<T> {
        self.node.map(|node| unsafe {
            let node = Box::from_raw(node.as_ptr());
            if self.size == 1 {
                self.node = None;
            } else {
                let (prev, next) = (node.prev().unwrap().as_ptr(), node.next().unwrap().as_ptr());
                (*prev).set_next(node.next());
                (*next).set_prev(node.prev());
                self.node = node.prev();
            }
            self.size -= 1;
            N::unwrap(node)
        })
    }

    fn size(&self) -> u64 {
        self.size
    }

    #[inline]
    fn insert(&mut self, pos: u64, val: T) {
        match self.node {
            None => self.push(val),
            Some(node) => unsafe {
                let p = pos % self.size;
                let (prev, next) = match (2 * p) < self.size {
                    true => {
                        let ptr = (*node.as_ptr()).next_nth(p).unwrap().as_ptr();
                        ((*ptr).prev().unwrap().as_ptr(), ptr)
                    }
                    false => {
                        let ptr = (*node.as_ptr()).prev_nth(self.size - p).unwrap().as_ptr();
                        ((*ptr).prev().unwrap().as_ptr(), ptr)
                    }
                };
                let boxed = N::create(val);
                let node: Option<NonNull<N>> = Some(Box::leak(boxed).into());
                let pnode = node.unwrap().as_ptr();
                (*pnode).set_prev((*next).prev());
                (*pnode).set_next((*prev).next());
                (*next).set_prev(node);
                (*prev).set_next(node);
                self.size += 1;
            },
        }
    }

    #[inline]
    fn delete(&mut self, pos: u64) -> Option<T> {
        match self.node {
            None => None,
            Some(node) => unsafe {
                match pos % self.size {
                    0 => self.pop(),
                    n => {
                        let (prev, node) = match (2 * n) < self.size {
                            true => {
                                let ptr = (*node.as_ptr()).next_nth(n).unwrap().as_ptr();
                                ((*ptr).prev().unwrap().as_ptr(), Box::from_raw(ptr))
                            }
                            false => {
                                let ptr =
                                    (*node.as_ptr()).prev_nth(self.size - n).unwrap().as_ptr();
                                ((*ptr).prev().unwrap().as_ptr(), Box::from_raw(ptr))
                            }
                        };

                        (*prev).set_next(node.next());
                        (*node.next().unwrap().as_ptr()).set_prev(node.prev());
                        self.size -= 1;
                        Some(N::unwrap(node))
                    }
                }
            },
        }
    }

    #[inline]
    fn clear(&mut self) {
        *self = Self::new();
    }

    #[inline]
    fn update(&mut self, pos: u64, val: T) {
        if self.size > 0 {
            unsafe {
                match pos % self.size {
                    0 => (*self.node.unwrap().as_ptr()).set_value(val),
                    n if (2 * n) < self.size => {
                        let node = (*self.node.unwrap().as_ptr()).next_nth(n);
                        (*node.unwrap().as_ptr()).set_value(val)
                    }
                    n => {
                        let node = (*self.node.unwrap().as_ptr()).prev_nth(self.size - n);
                        (*node.unwrap().as_ptr()).set_value(val)
                    }
                }
            }
        }
    }

    #[inline]
    fn at(&self, pos: u64) -> Option<T> {
        if self.size == 0 {
            None
        } else {
            unsafe {
                match pos % self.size {
                    0 => Some((*self.node.unwrap().as_ptr()).value()),
                    n if (2 * n) < self.size => {
                        let node = (*self.node.unwrap().as_ptr()).next_nth(n);
                        Some((*node.unwrap().as_ptr()).value())
                    }
                    n => {
                        let node = (*self.node.unwrap().as_ptr()).prev_nth(self.size - n);
                        Some((*node.unwrap().as_ptr()).value())
                    }
                }
            }
        }
    }

    #[inline]
    fn swap(&mut self, x: u64, y: u64) {
        let (x, y) = (x % self.size, y % self.size);
        if x != y {
            unsafe {
                let (x, y) = match x < y {
                    true => (x, y),
                    false => (y, x),
                };
                let (px, py) = match 2 * x > self.size {
                    true => {
                        let node_y = (*self.node.unwrap().as_ptr()).prev_nth(self.size - y);
                        let _py = node_y.unwrap().as_ptr();
                        let _px = (*_py).prev_nth(y - x).unwrap().as_ptr();
                        (_px, _py)
                    }
                    false => {
                        let _px = (*self.node.unwrap().as_ptr()).next_nth(x).unwrap().as_ptr();
                        let _py = match y {
                            y if (2 * y) > (self.size + x) => (*self.node.unwrap().as_ptr())
                                .prev_nth(self.size - y)
                                .unwrap()
                                .as_ptr(),
                            y => (*_px).next_nth(y - x).unwrap().as_ptr(),
                        };
                        (_px, _py)
                    }
                };
                let tmp = (*px).value();
                (*px).set_value((*py).value());
                (*py).set_value(tmp);
            }
        }
    }

    #[inline]
    fn to_vector(&self) -> Vec<T> {
        let mut container = Vec::<T>::with_capacity(self.size as usize);
        unsafe {
            let mut node = self.node;
            while let Some(n) = node {
                container.push((*n.as_ptr()).value());
                node = (*n.as_ptr()).next();
                if node == self.node {
                    break;
                }
            }
        }
        container
    }
}

impl<N> Ring<N> {
    #[inline]
    pub fn roll<T>(&mut self, pos: i64)
    where
        T: Clone + Sized,
        N: NodeBase<T>,
    {
        if self.size > 0 {
            let pos = match pos > 0 {
                true => pos as u64 % self.size,
                false => self.size - (-pos) as u64 % self.size,
            };
            match pos {
                0 => {}
                n if (2 * n) < self.size => unsafe {
                    self.node = (*self.node.unwrap().as_ptr()).next_nth(n)
                },
                n => unsafe { self.node = (*self.node.unwrap().as_ptr()).prev_nth(self.size - n) },
            }
        }
    }
}

#[derive(Clone, Default)]
pub struct List<T> {
    size: u64,
    block_size: u64,
    data: Vec<T>,
}

impl<T> List<T>
where
    T: Clone + Sized + Default,
{
    #[inline]
    fn increase(&mut self) {
        self.data
            .resize_with((self.size + self.block_size) as usize, Default::default);
    }

    #[inline]
    fn is_full(&self) -> bool {
        self.size as usize == self.data.capacity()
    }
}

impl<T> ChainBase<T> for List<T>
where
    T: Clone + Sized + Default,
{
    #[inline]
    fn new() -> Self {
        let size = match size_of::<T>() {
            0..=32 => 32,
            33..=128 => 16,
            129..=1024 => 4,
            _ => 1,
        };
        List {
            size: 0,
            block_size: size,
            data: Vec::with_capacity(size as usize),
        }
    }

    #[inline]
    fn push_head(&mut self, val: T) {
        if !self.is_full() {
            self.increase()
        }
        unsafe {
            let ptr = self.data.as_mut_ptr();
            copy(ptr, ptr.add(1), self.size as usize);
            write(ptr, val);
        }
        self.size += 1;
    }

    #[inline]
    fn pop_head(&mut self) -> Option<T> {
        match self.size {
            0 => None,
            _ => unsafe {
                let value = self.data[0].clone();
                self.size -= 1;
                let ptr = self.data.as_mut_ptr();
                copy(ptr.add(1), ptr, self.size as usize);
                Some(value)
            },
        }
    }

    #[inline]
    fn push(&mut self, val: T) {
        if !self.is_full() {
            self.increase()
        }
        unsafe {
            let ptr = self.data.as_mut_ptr().add(self.size as usize);
            write(ptr, val);
        }
        self.size += 1;
    }

    #[inline]
    fn pop(&mut self) -> Option<T> {
        match self.size {
            0 => None,
            _ => {
                let value = self.data[self.size as usize - 1].clone();
                self.size -= 1;
                Some(value)
            }
        }
    }

    #[inline]
    fn size(&self) -> u64 {
        self.size
    }

    #[inline]
    fn insert(&mut self, pos: u64, val: T) {
        assert!(pos <= self.size, "insertion is out of index");
        if pos == self.size {
            self.push(val)
        } else {
            if !self.is_full() {
                self.increase()
            }
            unsafe {
                let ptr = self.data.as_mut_ptr().add(pos as usize);
                copy(ptr, ptr.add(1), (self.size - pos) as usize);
                write(ptr, val);
            }
            self.size += 1;
        }
    }

    #[inline]
    fn delete(&mut self, pos: u64) -> Option<T> {
        match pos {
            0 => self.pop_head(),
            n if n == self.size - 1 => self.pop(),
            n if n >= self.size => None,
            n => unsafe {
                let value = self.data[n as usize].clone();
                self.size -= 1;
                let ptr = self.data.as_mut_ptr().add(n as usize);
                copy(ptr.add(1), ptr, self.size as usize);
                Some(value)
            },
        }
    }

    #[inline]
    fn clear(&mut self) {
        self.size = 0;
        self.data.clear();
    }

    #[inline]
    fn update(&mut self, pos: u64, val: T) {
        if pos < self.size {
            unsafe { write(self.data.as_mut_ptr().add(pos as usize), val) }
        }
    }

    #[inline]
    fn at(&self, pos: u64) -> Option<T> {
        match pos >= self.size {
            true => None,
            false => Some(self.data[pos as usize].clone()),
        }
    }

    #[inline]
    fn swap(&mut self, x: u64, y: u64) {
        assert!(x < self.size && y < self.size, "invalid index for chain");
        unsafe {
            let (px, py) = (
                self.data.as_mut_ptr().add(x as usize),
                self.data.as_mut_ptr().add(y as usize),
            );
            let (vx, vy) = (self.at(x).unwrap(), self.at(y).unwrap());
            write(px, vy);
            write(py, vx);
        }
    }

    #[inline]
    fn to_vector(&self) -> Vec<T> {
        self.data.clone()
    }
}

pub trait QSort<T>: ChainBase<T> {
    fn qsort(&mut self, lo: u64, hi: u64);
    fn reverse(&mut self);
    fn posit(&mut self, p: u64, lo: u64, hi: u64) -> u64;
}

impl<T, N> QSort<T> for N
where
    T: Clone + Sized + Ord,
    N: ChainBase<T>,
{
    fn qsort(&mut self, lo: u64, hi: u64) {
        if lo < hi {
            let p = self.posit((lo + hi) / 2, lo, hi);
            self.qsort(lo, p - 1);
            self.qsort(p + 1, hi);
        }
    }

    #[inline]
    fn reverse(&mut self) {
        let size = self.size();
        if size > 1 {
            for i in 0..(size / 2) {
                self.swap(i, size - i - 1);
            }
        }
    }

    #[inline]
    fn posit(&mut self, p: u64, lo: u64, hi: u64) -> u64 {
        self.swap(lo, p);
        let (mut p, mut j) = (lo, hi);
        while p != j {
            match p < j {
                true => {
                    if self.at(p) <= self.at(j) {
                        j -= 1;
                    } else {
                        self.swap(p, j);
                        swap(&mut p, &mut j);
                        j += 1;
                    }
                }
                false => {
                    if self.at(p) >= self.at(j) {
                        j += 1;
                    } else {
                        self.swap(p, j);
                        swap(&mut p, &mut j);
                        j -= 1;
                    }
                }
            }
        }
        p
    }
}

pub trait Sort<T>: QSort<T> {
    fn sort(&mut self, ascending: bool);
}

impl<T: Clone + Sized, N: QSort<T>> Sort<T> for N {
    #[inline]
    fn sort(&mut self, ascending: bool) {
        self.qsort(0, self.size() - 1);
        if !ascending {
            self.reverse();
        }
    }
}

impl<C, T> Search<T> for C
where
    T: Clone + Sized + PartialEq,
    C: ChainBase<T>,
{
    #[inline]
    fn index(&self, val: &T) -> Option<u64> {
        self.index_from(val, 0)
    }

    #[inline]
    fn index_from(&self, val: &T, offset: u64) -> Option<u64> {
        let (mut pos, size) = (offset, self.size());
        while pos < size && !val.eq(&self.at(pos).unwrap()) {
            pos += 1;
        }
        match pos {
            n if n == size => None,
            _ => Some(pos),
        }
    }

    #[inline]
    fn index_last_of(&self, val: &T) -> Option<u64> {
        let mut pos = self.size() - 1;
        while pos > 0 && !val.eq(&self.at(pos).unwrap()) {
            pos -= 1;
        }
        match pos > 0 || val.eq(&self.at(pos).unwrap()) {
            true => Some(pos),
            false => None,
        }
    }

    #[inline]
    fn count(&self, val: &T) -> u64 {
        let (mut count, mut pos, size) = (0, 0, self.size());
        while pos < size {
            if val.eq(&self.at(pos).unwrap()) {
                count += 1;
            }
            pos += 1;
        }
        count
    }
}
